import java.util.ArrayList;
import java.util.List;

/**
 * @ClassName LC46
 * @Author ykx
 * @Date 2024/3/28 7:15
 * @Version 1.0
 */
public class LC46 {
    public static void main(String[] args) {
        LC46 lc46 = new LC46();
        System.out.println(lc46.permute(new int[]{1, 2, 3}));
    }

    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        int[] ints = new int[nums.length];
        solve(result, ints, nums, 0);
        return result;
    }

    private void solve(List<List<Integer>> result, int[] ints, int[] nums, int n) {
        if (n == nums.length) {
            result.add(toList(ints));
        } else {
            for (int i = 0; i < nums.length; i++) {
                ints[n] = nums[i];
                if (isValid(ints, n)) {
                    solve(result, ints, nums, n + 1);
                }
            }
        }
    }

    private List<Integer> toList(int[] ints) {
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < ints.length; i++) {
            list.add(ints[i]);
        }
        return list;
    }

    private boolean isValid(int[] ints, int n) {
        for (int i = 0; i <= n; i++) {
            for (int j = i + 1; j <= n; j++) {
                if (ints[i] == ints[j]) {
                    return false;
                }
            }
        }
        return true;
    }

}
